Datenstruktur Feld, Suchen & Sortieren

IN-SA TB #018/024–027

---

Datenstruktur Feld (Array / Liste)

Was ist ein Feld?

Die Datenstruktur Feld (in anderen Sprachen: Array / Feld) speichert eine beliebige Anzahl von Elementen, die im Speicher aneinandergefügt werden.

Elemente werden über einen Index angesprochen (beginnt bei 0).

Index:  [0]  [1]  [2]  [3]  [4]  [5]  [6]
Werte:   1    2    5    9    1    7   11

Wichtige Operationen in Python

x = [1, 2, 5, 3, 9, 7, 1, 18, 3, 27, 5, 12, 18]

# Länge
len(x)          # Anzahl der Elemente

# Einzelnes Element abrufen
print(x[0])     # → 1
print(x[6])     # → 3

# Über alle Elemente iterieren
for i in x:
    print(i)

# Mit Index iterieren
for i in range(len(x)):
    print(x[i])

# Bedingung prüfen
for i in range(len(x)):
    if x[i] == 7:
        print("super", i)

# Element hinzufügen
x.append(11)    # fügt 11 ans Ende an

# Element an Index ändern
x[4] = 67

# Mit Zufallswerten befüllen
import random
for i in range(11):
    x[i] = random.randint(0, 10)  # Zufallswert 0–10

---

Suchen

① Sequentielle / Lineare Suche

Jedes Element des Feldes wird mit dem Gesuchten verglichen, bis es gefunden oder sein Nichtvorhandensein bestätigt wird.

Fall	Vergleiche
Best Case	1 Element
Average Case	n/2 Elemente
Worst Case	n Elemente

Bei großen Datensätzen kann die Suche entsprechend lange dauern.

def linSearch(n, liste):
    i = 0
    while i <= len(liste) - 1:
        if liste[i] == n:
            return i
        i += 1
    return -1

---

② Binäre Suche

Die binäre Suche halbiert bei jedem Schritt den Suchbereich. Das Feld muss sortiert sein!

Prinzip

Feld: [3, 4, 8, 10, 12, 13, 16, 18, 67]
       0   1   2   3   4   5   6   7   8

Gesucht: x = 16

Schritt 1: m = (0+8)/2 = 4  →  Feld[4] = 12  →  12 < 16  →  l = m+1 = 5
Schritt 2: m = (5+8)/2 = 6  →  Feld[6] = 16  →  GEFUNDEN!

Implementierung (rekursiv)

def binSearch(x, liste, l, r):
    if l > r:
        return -1           # nicht gefunden
    m = (l + r) // 2
    if liste[m] == x:
        return m
    elif liste[m] < x:
        return binSearch(x, liste, m + 1, r)
    else:
        return binSearch(x, liste, l, m - 1)

Wichtigste Unterschiede: Lineare vs. Binäre Suche

	Lineare Suche	Binäre Suche
Voraussetzung	Kein sortiertes Feld nötig	Feld muss sortiert sein
Aufwand (Worst Case)	O(n)	O(log n)
Prinzip	Element für Element	Halbieren des Suchbereichs

---

Sortieren

① Selection Sort (Auswahlsortieren)

Prinzip: Finde in jedem Durchlauf das Minimum des noch unsortierten Teils und tausche es an die richtige Stelle.

def selectionSort(feld):
    for i in range(len(feld)):
        mindex = i
        for j in range(i, len(feld)):
            if feld[mindex] > feld[j]:
                mindex = j
        # Tausch
        hilf = feld[i]
        feld[i] = feld[mindex]
        feld[mindex] = hilf

Fall	Laufzeit
Best Case	O(n²)
Average Case	O(n²)
Worst Case	O(n²)

---

② Insertion Sort (Einfügesortieren)

Prinzip: Füge jedes Element an die richtige Stelle im bereits sortierten Teil ein.

def insertionSort(feld):
    for i in range(len(feld)):
        for j in range(i, 0, -1):
            if feld[j] < feld[j - 1]:
                hilf = feld[j]
                feld[j] = feld[j - 1]
                feld[j - 1] = hilf

Fall	Laufzeit
Best Case	O(n)
Average Case	O(n²)
Worst Case	O(n²)

---

③ Bubble Sort

Prinzip: Vergleiche benachbarte Elemente und tausche sie, wenn sie in der falschen Reihenfolge sind. Große Elemente „blubbern" nach oben.

def bubbleSort(feld):
    for i in range(len(feld)):
        getauscht = False
        for j in range(len(feld) - 1 - i):
            if feld[j] > feld[j + 1]:
                hilf = feld[j]
                feld[j] = feld[j + 1]
                feld[j + 1] = hilf
                getauscht = True
        if not getauscht:
            break   # Optimierung: kein Tausch → fertig

Fall	Laufzeit
Best Case	O(n) – dank Optimierung
Average Case	O(n²)
Worst Case	O(n²)

---

Der Aufwand von Algorithmen (Komplexität)

Der Aufwand eines Algorithmus ist abhängig von der Anzahl der Ausführungen von Befehlen (in Abhängigkeit von der Eingabegröße n).

O-Notation (Landau-Notation)

Bezeichnung	Notation	Beispiel
Konstante Laufzeit	O(1)	x = x + 1 (einmal)
Lineare Laufzeit	O(n)	eine Schleife über n
Quadratische Laufzeit	O(n²)	zwei verschachtelte Schleifen über n

Beispiele

x = x + 1                          # t(n) = 1        → O(1)

for i in range(5):
    x = x + 1                      # t(n) = 5        → O(1) (konstant)

for i in range(n):
    x = x + 1                      # t(n) = n        → O(n)

for i in range(5):
    for j in range(6):
        x = x + 1                  # t(n) = 30       → O(1) (konstant)

for i in range(n):
    for j in range(n):
        x = x + 1                  # t(n) = n²       → O(n²)

# Kombination:
x = x + 1
for i in range(n):
    x = x + 1                      # t(n) = 1 + n + n² → O(n²) (dominanter Term)
for j in range(n):
    for k in range(n):
        x = x + 1

Vergleich für n = 10, 100, 1000, 1 000 000

n	O(n²) = n²
10	100
100	10.000
1.000	1.000.000
1.000.000	10¹²

Bei quadratischem Aufwand wächst die Laufzeit extrem schnell!

---

Vergleich der Sortieralgorithmen

Algorithmus	Best Case	Average Case	Worst Case	Stabil?
Selection Sort	O(n²)	O(n²)	O(n²)	✗
Insertion Sort	O(n)	O(n²)	O(n²)	✓
Bubble Sort	O(n)	O(n²)	O(n²)	✓
Merge Sort	O(n log n)	O(n log n)	O(n log n)	✓
Quicksort	O(n log n)	O(n log n)	O(n²)	✗

Ein Sortieralgorithmus heißt stabil, wenn gleichwertige Elemente ihre ursprüngliche Reihenfolge behalten.